{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 栈的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    max_size = 16\n",
    "    cur_size = 0\n",
    "    array = [None] * max_size\n",
    "    \n",
    "    def push(self, e):\n",
    "        if self.cur_size == self.max_size:\n",
    "            self.max_size *= 2\n",
    "            newArray = [None] * self.max_size\n",
    "            for i in range(self.cur_size):\n",
    "                newArray[i] = self.array[i]\n",
    "            self.array = newArray\n",
    "        self.array[self.cur_size] = e\n",
    "        self.cur_size += 1\n",
    "        \n",
    "    def pop(self):\n",
    "        if self.cur_size == 0:\n",
    "            return\n",
    "        else:\n",
    "            self.cur_size -= 1\n",
    "            return self.array[self.cur_size]\n",
    "        \n",
    "    def top(self):\n",
    "        if self.cur_size == 0:\n",
    "            return\n",
    "        else:\n",
    "            return self.array[self.cur_size - 1]\n",
    "    \n",
    "    def size(self):\n",
    "        return self.cur_size\n",
    "    \n",
    "    def empty(self):\n",
    "        self.cur_size = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "mystack = Stack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "mystack.push(2)\n",
    "mystack.push(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "2"
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mystack.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "3"
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mystack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "2"
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mystack.top()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "mystack.empty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "0"
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mystack.size()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 224. 基本计算器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "实现一个基本的计算器来计算一个简单的字符串表达式的值。\n",
    "\n",
    "字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格  。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: \"1 + 1\"\n",
    "输出: 2\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: \" 2-1 + 2 \"\n",
    "输出: 3\n",
    "\n",
    "示例 3:\n",
    "\n",
    "输入: \"(1+(4+5+2)-3)+(6+8)\"\n",
    "输出: 23\n",
    "\n",
    "说明：\n",
    "\n",
    "你可以假设所给定的表达式都是有效的。\n",
    "请不要使用内置的库函数 eval。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate(input_str):\n",
    "    num_stack = []\n",
    "    sign_stack = []\n",
    "    last = ''\n",
    "    for i in range(len(input_str) + 1):\n",
    "        if i == len(input_str):\n",
    "            char = 'end'\n",
    "        else:\n",
    "            char = input_str[i]\n",
    "        if char == '(':\n",
    "            sign_stack.append(char)\n",
    "        elif char == '+' or char == '-' or char == ')' or char == 'end':\n",
    "            if len(sign_stack) > 0 and (sign_stack[-1] == '+' or sign_stack[-1] == '-'):\n",
    "                sign = sign_stack.pop()\n",
    "                num2 = num_stack.pop()\n",
    "                num1 = num_stack.pop()\n",
    "                if sign == '+':\n",
    "                    num_stack.append(num1 + num2)\n",
    "                else:\n",
    "                    num_stack.append(num1 - num2)\n",
    "            if char == ')' and sign_stack[-1] == '(':\n",
    "                sign = sign_stack.pop()\n",
    "            else:\n",
    "                sign_stack.append(char)\n",
    "        elif char >= '0' and char <= '9':\n",
    "            num = int(char)\n",
    "            if last >= '0' and last <= '9':\n",
    "                num = num_stack.pop() * 10 + num\n",
    "            num_stack.append(num)\n",
    "        last = char\n",
    "    \n",
    "    return num_stack.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "-15"
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate('1-(32-16)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "24"
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "calculate('(12 + (4 + 5 + 2) - 13) + (6 + 8)')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "思考题：增加*和/运算，增加!运算，增加括号{}[]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 456. 132模式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。\n",
    "\n",
    "注意：n 的值小于15000。\n",
    "\n",
    "示例1:\n",
    "\n",
    "输入: [1, 2, 3, 4]\n",
    "\n",
    "输出: False\n",
    "\n",
    "解释: 序列中不存在132模式的子序列。\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: [3, 1, 4, 2]\n",
    "\n",
    "输出: True\n",
    "\n",
    "解释: 序列中有 1 个132模式的子序列： [1, 4, 2].\n",
    "\n",
    "示例 3:\n",
    "\n",
    "输入: [-1, 3, 2, 0]\n",
    "\n",
    "输出: True\n",
    "\n",
    "解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 遍历解法，3左边寻找1，O(n)，3右边寻找2，O(n^2)\n",
    "def find_132_pattern(nums):\n",
    "    length = len(nums)\n",
    "    \n",
    "    left = [None] * length\n",
    "    left[0] = float('inf')\n",
    "    \n",
    "    for i in range(1, length - 1):\n",
    "        left[i] = min(nums[i - 1], left[i - 1])\n",
    "    \n",
    "    for i in range(length - 2, 0, -1):\n",
    "        for j in range(i + 1, length):\n",
    "            if nums[j] < nums[i] and nums[j] > left[i]:\n",
    "                return True\n",
    "    \n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "False"
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_132_pattern([1, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "False"
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_132_pattern([1, 2, 3, 4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_132_pattern([3, 1, 4, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "False"
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_132_pattern([5, 4, 4, 6, 3, 4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_132_pattern([1, 2, 3, 4, -1, -9, -5, -3, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.4 ms ± 368 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit find_132_pattern([1, 2, 3, 4] * 1000 + [2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 单调栈解法，维护一个单调递减的区间[left, right]\n",
    "def find_132_pattern2(nums):\n",
    "    stack = []\n",
    "    for i in nums:\n",
    "        if not stack or i < stack[-1][0]:\n",
    "            stack.append([i, i])\n",
    "        else:\n",
    "            left = stack[-1][0]\n",
    "            while stack and i > stack[-1][1]:\n",
    "                stack.pop()\n",
    "            if stack and i > stack[-1][0] and i < stack[-1][1]:\n",
    "                return True\n",
    "            stack.append([left, i])\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "False"
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_132_pattern2([1, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "False"
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_132_pattern2([5, 4, 4, 6, 3, 4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_132_pattern2([1, 2, 3, 4, -1, -9, -5, -3, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21.5 µs ± 2.31 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit find_132_pattern2([1, 2, 3, 4] * 1000 + [2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 单调栈解法，维护一个单调递减的中间数字栈\n",
    "def find_132_pattern3(nums):\n",
    "    stack = []\n",
    "    right = float('-inf')\n",
    "    for num in nums[::-1]:\n",
    "        if num < right:\n",
    "            return True\n",
    "        while stack and num > stack[-1]:\n",
    "            right = stack.pop()\n",
    "        stack.append(num)\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "False"
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_132_pattern3([1, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "False"
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_132_pattern3([5, 4, 4, 6, 3, 4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_132_pattern3([1, 2, 3, 4, -1, -9, -5, -3, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "34.8 µs ± 6.93 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit find_132_pattern3([1, 2, 3, 4] * 1000 + [2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 20. 有效的括号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。\n",
    "\n",
    "有效字符串需满足：\n",
    "\n",
    "左括号必须用相同类型的右括号闭合。\n",
    "左括号必须以正确的顺序闭合。\n",
    "注意空字符串可被认为是有效字符串。\n",
    "\n",
    "示例 1:\n",
    "\n",
    "输入: \"()\"\n",
    "输出: true\n",
    "\n",
    "示例 2:\n",
    "\n",
    "输入: \"()[]{}\"\n",
    "输出: true\n",
    "\n",
    "示例 3:\n",
    "\n",
    "输入: \"(]\"\n",
    "输出: false\n",
    "\n",
    "示例 4:\n",
    "\n",
    "输入: \"([)]\"\n",
    "输出: false\n",
    "\n",
    "示例 5:\n",
    "\n",
    "输入: \"{[]}\"\n",
    "输出: true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_valid(string):\n",
    "    stack = []\n",
    "    pair_dict = {')':'(', '}':'{', ']':'['}\n",
    "    for i in string:\n",
    "        if i in pair_dict:\n",
    "            if stack[-1] == pair_dict[i]:\n",
    "                stack.pop()\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            stack.append(i)       \n",
    "    return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid('')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "False"
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid(' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid('()[]{}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "False"
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid('([)]')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_valid('{[]}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 402. 移掉K位数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。\n",
    "\n",
    "注意:\n",
    "\n",
    "num 的长度小于 10002 且 ≥ k。\n",
    "num 不会包含任何前导零。\n",
    "\n",
    "示例 1 :\n",
    "\n",
    "输入: num = \"1432219\", k = 3\n",
    "输出: \"1219\"\n",
    "解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。\n",
    "\n",
    "示例 2 :\n",
    "\n",
    "输入: num = \"10200\", k = 1\n",
    "输出: \"200\"\n",
    "解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。\n",
    "\n",
    "示例 3 :\n",
    "\n",
    "输入: num = \"10\", k = 2\n",
    "输出: \"0\"\n",
    "解释: 从原数字移除所有的数字，剩余为空就是0。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 二重循环遍历\n",
    "def remove_k_digits(nums, k):\n",
    "    left = 0\n",
    "    output = []\n",
    "    for j in range(k + 1, len(nums) + 1):\n",
    "        min_value = float('inf')\n",
    "        min_idx = 0\n",
    "        for i in range(left, j):\n",
    "            if int(nums[i]) < min_value:\n",
    "                min_value = int(nums[i])\n",
    "                min_idx = i\n",
    "        output.append(str(min_value))\n",
    "        left = min_idx + 1\n",
    "    \n",
    "    output = ''.join(output)\n",
    "    if output:\n",
    "        return int(output)\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "1219"
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "remove_k_digits(\"1432219\", 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "200"
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "remove_k_digits(\"10200\", 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "0"
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "remove_k_digits(\"10\", 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22.8 µs ± 848 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit remove_k_digits(\"143237924739247927832219\", 12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 单调栈，一次遍历，将所有比当前数字小的数出栈，并统计出栈次数是否达到k\n",
    "def remove_k_digits2(nums, k):\n",
    "    stack = []\n",
    "    for i in nums:\n",
    "        while k > 0 and stack and stack[-1] > i:\n",
    "            stack.pop()\n",
    "            k -= 1\n",
    "        stack.append(i)\n",
    "        \n",
    "    stack = ''.join(stack)\n",
    "    if stack:\n",
    "        return int(stack)\n",
    "    else:\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "1219"
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "remove_k_digits2(\"1432219\", 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "200"
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "remove_k_digits2(\"10200\", 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "0"
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "remove_k_digits2(\"10\", 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6.66 µs ± 947 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit remove_k_digits2(\"143237924739247927832219\", 12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 946. 验证栈序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定 pushed 和 popped 两个序列，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。\n",
    "\n",
    " \n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]\n",
    "输出：true\n",
    "解释：我们可以按以下顺序执行：\n",
    "push(1), push(2), push(3), push(4), pop() -> 4,\n",
    "push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1\n",
    "\n",
    "示例 2：\n",
    "\n",
    "输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]\n",
    "输出：false\n",
    "解释：1 不能在 2 之前弹出。\n",
    " \n",
    "\n",
    "提示：\n",
    "\n",
    "0 <= pushed.length == popped.length <= 1000\n",
    "0 <= pushed[i], popped[i] < 1000\n",
    "pushed 是 popped 的排列。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "def validate_stack_sequences(pushed, popped):\n",
    "    stack = []\n",
    "    while pushed:\n",
    "        stack.append(pushed.pop(0))\n",
    "        while stack and popped[0] == stack[-1]:\n",
    "            stack.pop()\n",
    "            popped.pop(0)\n",
    "    return not stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "validate_stack_sequences([], [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "False"
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "validate_stack_sequences([1], [2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "validate_stack_sequences([1,2,3,4,5], [4,5,3,2,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "False"
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "validate_stack_sequences([1,2,3,4,5], [4,3,5,1,2])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "language": "python",
   "display_name": "Python 3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}